#include "main/utils.h"
using namespace std;

int findTargetSumWays(const vector<int>& arr, const int& target) {
  int sum = 0;
  for (auto ele : arr) {
    sum += ele;
  }
  if ((sum + target) % 2 || sum < target) {
    return 0;
  }

  int new_target = (sum + target) / 2;
  int len = arr.size();
  vector<int> dp(new_target + 1, 0);
  dp[0] = 1;
  for (int i = 1; i <= len; ++i) {
    for (int j = new_target; j >= arr[i - 1]; --j) {
      dp[j] = dp[j] + dp[j - arr[i - 1]];
    }
  }
  return dp[new_target];
}

int main() {
  vector<int> arr = {2, 2, 2};
  cout << findTargetSumWays(arr, 2) << endl;

  return 0;
}
